home *** CD-ROM | disk | FTP | other *** search
/ ftp.cs.arizona.edu / ftp.cs.arizona.edu.tar / ftp.cs.arizona.edu / icon / newsgrp / group94a.txt / 000111_icon-group-sender _Wed May 4 13:47:52 1994.msg < prev    next >
Internet Message Format  |  1994-08-19  |  2KB
  1. Received: by cheltenham.cs.arizona.edu; Wed, 4 May 1994 12:28:50 MST
  2. From: "Art Eschenlauer" <eschen@molbio.cbs.umn.edu>
  3. Message-Id: <9405041847.AA05442@molbio.cbs.umn.edu>
  4. Subject: pattern searching for molecular biology
  5. To: icon-group@cs.arizona.edu
  6. Date: Wed, 4 May 94 13:47:52 CDT
  7. X-Mailer: ELM [version 2.3test PL26]
  8. Status: R
  9. Errors-To: icon-group-errors@cs.arizona.edu
  10.  
  11. I have a molecular biology problem that I am trying to solve with Icon.
  12. It boils down to pattern searching. I suppose I should look up pattern
  13. matching algorithms in a real comp sci book, but if you wish to read
  14. further....
  15.  
  16. Genes consist of strings of bases A,C,G, and T. I want to look for patterns
  17. in those strings (patterns that are recognized by enzymes that cut the
  18. DNA at specific sequences in the DNA). So, I have a file of about 200
  19. different recognition sequences, e.g., EcoRI is an enzyme that recognizes
  20. and cuts at GAATTC sequences. Additionally, some of those recog seqs are
  21. redundant; for example, StyI recognizes CCWWGG, where W = A|T, and MslI
  22. recognizes CAYNNNNRTG, where Y = C|T, R = A|G, and N = A|C|G|T. Many recog
  23. seqs are about 6 bases, but they range from 4 to 15 bases.
  24.  
  25. I want a way to match these sequences that is efficient with memory and
  26. time. What is the FASTEST way to do this in Icon? The FIRST way that I
  27. can think of doing it is with string invocation, e.g.,
  28.  
  29. # &subject has gene sequence, and recog sites are found using
  30. #   every i := find( 
  31. #      ((site := SiteGeneratorFunction())[1:2])( site[2:0] )
  32. #      ) do { whatever }
  33. # # the [1:2] substring is taken to produce 
  34. # #    the 1 char name of the procedure to be invoked
  35.  
  36. # ... declare procedures A,B,C,D,G,H,K,M,N,R,S,T, and W
  37.  
  38. procedure Y(RestOfSite)
  39.    if RestOfSite == "" then return ""
  40.    suspend ( move(1) == ("C"|"T") ) || 
  41.       (RestOfSite[1:2])( RestOfSite[2:0] ) 
  42. end
  43.  
  44. (Please pardon [and point out] any gross errors ... I'm do not
  45. have perfect understanding of string scanning and generators yet.)
  46.  
  47. Will that be fast? Is there a faster algorithm that is obvious or some
  48. feature of Icon that I am missing? I hesitate to use coexpressions, since,
  49. for example, CAYNNNNRTG would produce 2^2 * 4^4 = 1024 results! 
  50.